
#include "HeapSort.h"
#include <stdio.h>

using namespace std;

HeapSort::HeapSort(int * array, int len):m_array(array), m_len(len)
{
	CreateHeap();
}

void HeapSort::Swap(int index1, int index2)
{
	int temp = m_array[index1];
	m_array[index1]= m_array[index2];
	m_array[index2]= temp;
}

void HeapSort::Print(int eleCount )
{
	if(eleCount == 0)
		eleCount = m_len;

	/*
	for(int i = 0; i < m_len ; i++)
		cout << m_array[i] << " ";

	cout << endl;

	*/
	long base = 1;
	int level = 0;

	while(eleCount > base)
	{
		base = base << 1;	
		level ++;
	}

	base = base >> 1;
	int count = 1;


	cout << "eleCount is " << eleCount <<  " Base is "<< base << " Level is " << level <<endl;
	int outputCount = 0;
	for(int i = 0 ; i < level; i++)
	{
		int padding = level-i-1;
		while(padding--)
			printf("   ");

		for(int j = 0; j < count; j++)
		{
			if(outputCount > eleCount-1)
				break;
			printf("%03d", m_array[outputCount++]);
			printf("   ");
		}

		count = count<<1;
		cout << endl;
	}

}

//Compare rootIndex and it's children.
void HeapSort::MaxHeapify(int lastParentIndex, int maxIndex)
{
	//找到最后一个有叶子结点的Node
	int rootIndex = lastParentIndex ;
	int leftChildIndex = rootIndex * 2 + 1;
	int rightChildIndex = rootIndex * 2 + 2;
	
	int biggerIndex = rootIndex;

	if((leftChildIndex <= maxIndex) && (m_array[leftChildIndex] > m_array[biggerIndex]))
	{
		biggerIndex = leftChildIndex;
	}

	if((rightChildIndex <= maxIndex) && (m_array[rightChildIndex] > m_array[biggerIndex]))
	{
		biggerIndex = rightChildIndex;
	}

	if(biggerIndex != rootIndex)
	{
		Swap(biggerIndex, rootIndex);
		MaxHeapify(biggerIndex, maxIndex);
	}
}

void HeapSort::CreateHeap()
{
	for(int i = m_len/2 - 1; i >= 0; i--)
	{
		MaxHeapify(i, m_len-1);
	}
}

void HeapSort::SortHeap()
{
	CreateHeap();
	/*此时栈顶0位置已经是最大值，所以循环一开始就与其交换，然后再调整成最大堆，此时最大可用索引要减一*/
	for (int i = m_len-1; i > 0; i--)
	{
		/*每执行一次循环，栈顶0的位置是最大数，因此再与最后一个交换形成，最后一个数存放的是当前循环的最大数。*/
		Swap(0, i);
		MaxHeapify(0, i-1);
	}

}

